package com.dexter.year2023.charpter1_linkedlist.level3.topic3_2双向链表;

/**
 * 双向链表相关：创建、遍历、插入、删除
 */
public class DoubleLinkedList {
    /**
     * 创建双向链表结点
     */
    public class DoubleNode {
        public int data; // 数据
        public DoubleNode next; // 下一结点
        public DoubleNode prev; // 上一结点

        public DoubleNode(int data) {
            this.data = data;
        }

        // 打印结点
        public void displayNode() {
            System.out.println("{" + data + "} ");
        }
    }

    // region 初始化、正（反）向遍历

    /**
     * 定义成员变量，头结点，尾结点
     */
    private DoubleNode first;
    public DoubleNode last;

    public DoubleLinkedList() {
        first = null;
        last = first;
    }

    public static void main(String[] args) {
        // 初始化
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        // 插入
        doubleLinkedList.insertFist(60);
        doubleLinkedList.insertFist(40);
        doubleLinkedList.insertFist(20);
        doubleLinkedList.insertLast(70);
        doubleLinkedList.insertLast(80);
        doubleLinkedList.insertLast(90);
        doubleLinkedList.insertAfter(40, 400);
        doubleLinkedList.insertAfter(60, 600);

        doubleLinkedList.displayForward();
        doubleLinkedList.displayBackward();
        System.out.println("====================================");

        // 删除
        doubleLinkedList.deleteFist();
        doubleLinkedList.deleteLast();
        doubleLinkedList.displayForward();
        doubleLinkedList.displayBackward();
        System.out.println("====================================");

        doubleLinkedList.deletekey(40);
        doubleLinkedList.deletekey(80);
        doubleLinkedList.insertAfter(600, 700);
        doubleLinkedList.displayForward();
        doubleLinkedList.displayBackward();
    }

    /**
     * 从头正向遍历
     */
    public void displayForward() {
        System.out.println("List(First--->Last): ");
        // 从头开始
        DoubleNode cur = first;
        while (cur != null) {
            cur.displayNode();
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 从尾反向遍历
     */
    public void displayBackward() {
        System.out.println("List(Last--->First): ");
        // 从尾开始
        DoubleNode cur = last;
        while (cur != null) {
            cur.displayNode();
            cur = cur.prev;
        }
        System.out.println();
    }

    // endregion

    // region 插入结点

    /**
     * 在头部插入
     *
     * @param data
     */
    public void insertFist(int data) {
        DoubleNode newDoubleNode = new DoubleNode(data);
        // 链表为空
        if (isEmpty()) {
            last = newDoubleNode;
        } else {
            // 往前插
            first.prev = newDoubleNode;
        }
        newDoubleNode.next = first;
        // 成为头结点
        first = newDoubleNode;
    }

    /**
     * 在尾部插入
     *
     * @param data
     */
    public void insertLast(int data) {
        DoubleNode newDoubleNode = new DoubleNode(data);
        // 链表为空
        if (isEmpty()) {
            first = newDoubleNode;
        } else {
            // 双向绑定
            newDoubleNode.prev = last;
            last.next = newDoubleNode;
        }
        // 成为尾结点
        last = newDoubleNode;
    }

    /**
     * 根据key插入中间结点
     *
     * @param key
     * @param data
     */
    public void insertAfter(int key, int data) {
        DoubleNode newDoubleNode = new DoubleNode(data);
        DoubleNode cur = first;
        // cur移动去找位置
        while (cur != null && cur.data != key) {
            cur = cur.next;
        }
        // 1. cur为空
        if (cur == null) {
            // 1.1 链表为空，成为头结点
            if (isEmpty()) {
                first = newDoubleNode;
                last = newDoubleNode;
            } else {
                // 1.2 找不到key，成为尾结点
                last.next = newDoubleNode;
                newDoubleNode.prev = last;
                last = newDoubleNode;
            }
        } else {
            // 2. 找到了key
            if (cur == last) {
                // 2.1 key与尾结点相等
                newDoubleNode.next = null;
                last = newDoubleNode;
            } else {
                // 2.2 两结点中间位置
                newDoubleNode.next = cur.next;
                cur.next.prev = newDoubleNode;
            }
            // 以上是处理newDoubleNode与下一结点连线，以下是处理上一结点与newDoubleNode连线
            cur.next = newDoubleNode;
            newDoubleNode.prev = cur;
        }
    }

    // endregion

    // region 删除结点

    /**
     * 删除头结点
     *
     * @return 已经删除的头结点
     */
    public DoubleNode deleteFist() {
        // 临时存放
        DoubleNode temp = first;
        if (first.next == null) {
            // 只有头结点
            last = null;
        } else {
            // 还有其他结点，first.next变成头结点
            first.next.prev = null;
        }
        first = first.next;
        return temp;
    }

    /**
     * 删除尾结点
     *
     * @return 已经删除的尾结点
     */
    public DoubleNode deleteLast() {
        // 临时存放
        DoubleNode temp = last;
        if (first.next == null) {
            // 只有头结点
            first = null;
        } else {
            // 还有其他结点，上一结点变尾结点
            last.prev.next = null;
        }
        last = last.prev;
        return temp;
    }

    /**
     * 根据key删除中间结点，cur.prev -- 要删除的是cur -- cur.next
     *
     * @param key 已经删除的中间结点
     * @return
     */
    public DoubleNode deletekey(int key) {
        DoubleNode cur = first;
        // cur去找位置
        while (cur != null && cur.data != key) {
            cur = cur.next;
        }
        if (cur == null) {
            return null;
        } else {
            // cur是第一个
            if (cur == first) {
                first = cur.next;
                cur.next.prev = null;
            } else if (cur == last) {
                // cur是最后一个
                last = cur.prev;
                cur.prev.next = null;
            } else {
                // cur是中间
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
        }
        return cur;
    }

    // endregion

    /**
     * 链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return (first == null);
    }
}
